package com.mlh.string;

import java.util.Arrays;

/**
 * @author 缪林辉
 * @date 2024/8/16 21:44
 * @DESCRIPTION
 */
//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
// 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
// 注意：
// 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
// 如果 s 中存在这样的子串，我们保证它是唯一的答案。
//  输入：s = "ADOBECODEBANC", t = "ABC"
// 输出："BANC"
// 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
public class 最小覆盖子串 {
    public String method1(String s, String t) {
        if(s.length()<t.length()){
            return "";
        }
        int[]sCount=new int[52],tCount=new int[52];
        for (int i = 0; i < t.length(); i++) {
            //大写字母 'A' 的ASCII码是65。
            // 小写字母 'a' 的ASCII码是97。
            ++tCount[t.charAt(i)-'A'];
        }
        int left=-1,right=-1;
        for (int i = 0; i < s.length(); i++) {
            ++sCount[s.charAt(i)-'A'];
            if(check(sCount,tCount)){
               right=i;//锁定右指针
                break;
            }
        }
        for (int i = 0; i <= right; i++) {
            --sCount[s.charAt(i)-'A'];
            if(!check(sCount,tCount)){
                left=i;//锁定左指针
                break;
            }
        }
        if(right==-1){
            return "";
        }
        return s.substring(left,right+1);
    }
    public boolean check(int[]sCount,int[]tCount){
        for (int i = 0; i < sCount.length; i++) {
            if(sCount[i]<tCount[i]){
                return false;
            }
        }
        return true;
    }
}
